1782. 统计点对的数目

Similar Question

Solution Tips

方案一: 模拟 (超时了)

var countPairs = function(n, edges, queries) {
    // 计算每个 pair 的边
    // pair 由全排列生成
    // 有必要构造图嘛? 直接遍历边就可以知道每个 node 有多少条边了, 两个 node 之间去重一下就行

    // 直接遍历 edges 记录
    const nodeMap = Array.from({length: n + 1}, () => []);
    for (let i = 0; i < edges.length; i++) {
        const [one, two] = edges[i];
        // 这题麻烦的是边的去重
        nodeMap[one].push(`${edges[i]},${i}`);
        nodeMap[two].push(`${edges[i]},${i}`);
    }
    // 不需要知道具体的 pair 是啥, 只需要统计出 pair 的边的数量就行
    // const nodePair = {};
    const nodePairIncidentList = [];
    // 全排列, 计算 incident(a, b)
    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            // 对于 pair(i,j), incident(i, j) 为 nodeMap(i, j) 去重
            nodePairIncidentList.push(new Set([...nodeMap[i], ...nodeMap[j]]).size);
        }
    }

    // 根据 query 查询
    // 对 nodePairIncidentList 进行排序, 快速找出大于 query[i] 的数目
    nodePairIncidentList.sort((a, b) => a - b);
    const pairLen = nodePairIncidentList.length;
    const res = queries.map((count) => {
        // 找到第一个比 count 大的数
        let index = 0;
        let find = false;
        for (let i = 0; i < pairLen; i++) {
            if (nodePairIncidentList[i] > count) {
                index = i;
                find = true;
                break;
            }
        }
        return find ? pairLen - index : 0;
    })

    return res;
};

// let n = 4, edges = [[1, 2], [2, 4], [1, 3], [2, 3], [2, 1]], queries = [2, 3];
let n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5];
console.log(countPairs(n, edges, queries))